package 回溯;

import java.util.ArrayList;
import java.util.List;

//https://leetcode.cn/problems/binary-watch/

public class 二进制手表 {
    //辅助DFS ，确定10个灯泡，你问我为啥好要放两个数组？因为h和m分开会面会好操作
    int[] hr = new int[]{1,2,4,8,0,0,0,0,0,0};
    int[] mr = new int[]{0,0,0,0,1,2,4,8,16,32};
    List<String> list = new ArrayList<>();


    public List<String> readBinaryWatch(int turnedOn) {
        return fun_enumerate_1(turnedOn);
        // 辅助DFS
        //fun_DFS(turnedOn , 0 , 0 , 0);
        //        return list;
    }
    public List<String> fun_enumerate_1(int turnedOn) {
        List<String> list = new ArrayList<>();
        for (int i = 0 ; i < 12 ; i++){
            for (int j = 0 ; j < 60 ; j++){
                if (Integer.bitCount(i) + Integer.bitCount(j) == turnedOn){
                    list.add(i + ":" + (j > 10 ? "0" : "") + j);
                }
            }
        }
        return list;
    }
    public void fun_DFS(int num , int j , int h , int m){
        //给定有几个led，剩余led的,//方便下一轮判断 ，下一次要判断的h与m
        if (h > 11 || m > 59){
            return;
        }
        //当然，如果num==0的话说明led用完了，而且截止目前h和m也都满足条件，所以时h和m表示的就是时间
        if (num == 0){
            list.add(h + ":" + (m < 10 ? "0" : "") + m);
            return;
        }
        for (int i = j ; i < 10 ; i++){
            fun_DFS(num - 1 , i + 1 , h + hr[i] , m + mr[i]);
        }
    }

}
